package graphesTOTEST;
/** Classe permettant de calculer des isomorphismes de graphes.
 * @author un client anonyme
 */
public class Isomorphisme {
	
	private Graphe g1;
	private Graphe g2;
	private Pile abscisse; //Isomorphisme
	private Pile ordonnee; //Isomorphisme
		
    public Isomorphisme(Graphe gg1, Graphe gg2) {
	  g1 = gg1;
	  g2 = gg2;
	  abscisse = new Pile();
	  ordonnee = new Pile();
    }
		  
    /**
     * Vérifie l'existence d'un isomorphisme entre les 2 graphes g1 et
     * g2 et le calcule.
     *
     */
    public boolean buidIsomorphisme() {
	// Calcul de l'ensemble des sommets de g1
	Ensemble E1 = new Ensemble();
	for (int i = 0; i < g1.NMAX; i++)
	    if (g1.existeSommet(i))
		    E1.ajoutElt(i);
	// Calcul de l'ensemble des sommets de g1
	Ensemble E2 = new Ensemble();
	for (int i = 0; i < g2.NMAX; i++)
	    if (g2.existeSommet(i))
		    E2.ajoutElt(i);
	return buildIsomorphisme(E1,E2);
    }


    /**
     * Vérifie l'existence d'un isomorphisme entre les ensemble de
     * sommets non encore associés W1 et W2 dans la construction
     * d'isomorphisme entre 2 graphes g1 et g2 et le calcule.
     *
     * @param W1 L'ensemble des sommets de g1 non encore associés
     * @param W2 L'ensemble des sommets de g2 non encore associés
     */    
    private boolean buildIsomorphisme(Ensemble W1, Ensemble W2) {
	    
	    boolean prop = false;
			    
	    if (W1.estVide() && W2.estVide()) {
			  prop = true;
		}
	    else {	  
		  //SOIT x UN SOMMET DE g1 DONT ON VEUT L'ISOMORPHISME
		  int x  = W1.element();
		  int y;
		  		    
		  //SOMMETS A EXPLORER
		  Ensemble W3 = new Ensemble(W2);
		  
		  //PARCOURS DE W3 et TEST DES ASSOCIATIONS x <-> element de W3
		  while ( (!prop) && (!W3.estVide()) ) {
			  
			  //RECUPERATION D'UN SOMMET y DE L'ENSEMBLE W3
			  y = W3.element();
			  W3.oterElt(y);
		  	  
			  //SI LE SOMMET y (de g2) EST LICITE
			  if (  g1.degreEntrant(x) == g2.degreEntrant(y) 
			     && g1.degreSortant(x) == g2.degreSortant(y) ) {

				//x isomorphe possible à y
				
				//SUPPRESSION DU SOMMET x de g1
				W1.oterElt(x);
				//SUPPRESSION DU SOMMET y de g2
				W2.oterElt(y);
				     				
				//CONSTRUCTION D'UN ISOMORPHISME ENTRE W1 et W2
			    prop = buildIsomorphisme(W1, W2);

			    if (!prop) {
					//x non isomorphe à y
				    W1.ajoutElt(x);
				}
				else {
			      //CONSTRUCTION DE L'ISOMORPHISME
				  abscisse.empiler(x);
				  ordonnee.empiler(y);
			    }
			  } //Fin if
		  } //Fin while
	    } //Fin else
	    
	    return prop;
    }
	 
    
    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    public String toString() {
    	return abscisse + "\n" + ordonnee;
    }
    
	public static void main(String[] args) {
 		int N = Graphe.ALPHA_NOTDEF;

 		int [][] matg0 = { /*         1   2   3   4   5   6   7*/
 						   /* 1 */ {  N,  N,  N,  N,  1,  1,  N},
 						   /* 2 */ {  N,  N,  1,  1,  1,  1,  N},
 						   /* 3 */ {  N,  1,  N,  N,  N,  N,  N},
 						   /* 4 */ {  N,  1,  N,  N,  N,  1,  N},
 						   /* 5 */ {  1,  1,  N,  N,  N,  N,  N},
 						   /* 6 */ {  1,  1,  N,  1,  N,  N,  N},
 						   /* 7 */ {  N,  N,  N,  N,  N,  N,  N}, };
 						   
 		int [][] matg1 = { /*         1   2   3   4   5   6   7*/
 						   /* 1 */ {  N,  1,  N,  N,  1,  1,  N},
 						   /* 2 */ {  1,  N,  N,  N,  1,  N,  N},
 						   /* 3 */ {  N,  N,  N,  N,  1,  1,  N},
 						   /* 4 */ {  N,  N,  N,  N,  1,  N,  N},
 						   /* 5 */ {  1,  1,  1,  1,  N,  N,  N},
 						   /* 6 */ {  1,  N,  1,  N,  N,  N,  N},
 						   /* 7 */ {  N,  N,  N,  N,  N,  N,  N}, };

 		Graphe g0   = new Graphe (matg0);
		Ensemble E0 = new Ensemble();
		E0.ajoutElt(0); 		
		E0.ajoutElt(1); 		
		E0.ajoutElt(2); 		
		E0.ajoutElt(3); 		
		E0.ajoutElt(4); 		
		E0.ajoutElt(5); 		
		E0.ajoutElt(6); 		

 		Graphe g1   = new Graphe (matg1);
		Ensemble E1 = new Ensemble(E0);
		
 		
 		Isomorphisme iso = new Isomorphisme(g0,g1);
 		iso.buildIsomorphisme(E0,E1);
 		System.out.println(iso);

 		
 		
 	}
    
}   